package leetcode.editor.day;

// 687. 最长同值路径
// https://leetcode.cn/problems/longest-univalue-path/
class LongestUnivaluePath {
    public static void main(String[] args) {
        Solution solution = new LongestUnivaluePath().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        public int longestUnivaluePath(TreeNode root) {
            dfs(root);
            return max;
        }

        int max = 0;    // 记录长度

        public int dfs(TreeNode root) {
            if (root == null) return 0;
            // 后序遍历
            int left = dfs(root.left);
            int right = dfs(root.right);

            // 比较左右节点和父节点的值来求出长度
            if (root.left != null && root.right != null && root.val == root.left.val && root.val == root.right.val) {
                max = Math.max(left + right, max);
                return 1 + Math.max(left, right);
            } else if (root.left != null && root.val == root.left.val) {
                max = Math.max(left, max);
                return 1 + left;
            } else if (root.right != null && root.val == root.right.val) {
                max = Math.max(right, max);
                return 1 + right;
            }

            return 1;
        }

        // 官解的写法，思路一样，但更加简洁
        // https://leetcode.cn/problems/longest-univalue-path/solution/zui-chang-tong-zhi-lu-jing-by-leetcode-s-hgfk/
        public int dfs1(TreeNode root) {
            if (root == null) return 0;
            int left = dfs1(root.left);
            int right = dfs1(root.right);
            int left1 = 0,  right1 = 0;
            if (root.left != null && root.val == root.left.val) left1 = left + 1;
            if (root.right != null && root.val == root.right.val) right1 = right + 1;
            max = Math.max(max, left1 + right1);
            return Math.max(left1, right1);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
